/*
 * Copyright (c)e 2024-2024.Powered by 清明雨揽月
 * This software is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan
 * PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *          http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN 'AS IS' BASIS, WITHOUT WARRANTIES OF ANY
 * KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
 * NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
 */

//
// Created by Nefilibata on 2024/8/26.
//

#include "sort.h"

#include <deque>
#include <iostream>

/**
 * ShellSort:希尔排序
 * 一种不稳定的排序算法，仅适用于顺序存储的线性表
 * @param arr
 * @param n
 */
void Sort::shellSort(int arr[], const int n)
{
    int dk, i, j;
    for (dk = n / 2; dk >= 1; dk = dk / 2)
    {
        for (i = dk + 1; i <= n; ++i)
        {
            if (arr[i] < arr[i - dk])
            {
                arr[0] = arr[i];
                for (j = i - dk; j > 0 && arr[0] < arr[j]; j -= dk)
                {
                    arr[j + dk] = arr[j];
                }
                arr[j + dk] = arr[0];
            }
        }
    }
}

/**
 * InsertSort:直接插入排序
 * 一种稳定的排序算法，适用于顺序存储和链式存储的线性表，采用链式存储时无需移动元素
 * @param arr
 * @param n
 */
void Sort::insertSort(int arr[], const int n)
{
    int i, j;
    std::cout << "Sort start" << std::endl;
    for (i = 2; i <= n; i++)
    {
        if (arr[i] < arr[i - 1])
        {
            arr[0] = arr[i];
            for (j = i - 1; arr[0] < arr[j]; --j)
            {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = arr[0];
        }
    }
    std::cout << "Sort end" << std::endl;
    for (i = 0; i < n; i++)
    {
        std::cout << arr[i] << "\f\f";
    }
}

/**
 * InsertSortPlus:折半插入排序
 * 一种稳定的排序算法，仅适用于顺序存储的线性表
 * @param arr
 * @param n
 */
void Sort::insertSortPlus(int arr[], const int n)
{
    int i, j, low, high, mid;
    for (i = 2; i < n; i++)
    {
        arr[0] = arr[i];
        low = 1;
        high = i - 1;
        while (low <= high)
        {
            mid = (high - low) / 2;
            if (arr[mid] < arr[0])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (j = i - 1; j > high + 1; --j)
        {
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = arr[0];
    }
}

/**
 * BubbleSort:冒泡排序
 * 一种稳定的排序算法，适用于顺序存储和链式存储的线性表
 * @param arr
 * @param n
 */
void Sort::bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
        {
            if (arr[j - 1] > arr[j])
            {
                std::swap(arr[j - 1], arr[j]);
                flag = true;
            }
            if (flag == false)
            {
                return;
            }
        }
    }
}

/**
 * Partition:快速排序中划分操作的应用
 * 将总表划分为子表
 * @param arr
 * @param low
 * @param high
 */
int Sort::partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] > pivot)
        {
            --high;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot)
        {
            ++low;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

/**
 * QuickSort:快速排序
 * 一种不稳定的排序算法，但是是所有内部排序算法中平均性能最优的排序算法，仅适用于顺序存储的线性表
 * @param arr
 * @param low
 * @param high
 */
void Sort::quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

/**
 * SelectSort:简单选择排序
 * 一种不稳定的排序算法，适用于顺序存储和链式存储的线性表，以及关键字较少的情况
 * @param arr
 * @param n
 */
void Sort::selectSort(int arr[], const int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
            if (min != i)
            {
                std::swap(arr[i], arr[min]);
            }
        }
    }
}

/**
 * HeadSort:堆排序
 * 一种不稳定的排序算法，仅适用于顺序存储的线性表
 * @param arr
 * @param len
 */
void Sort::heapSort(int arr[], const int len)
{
    buildMaxHeap(arr, len);
    for (int i = len; i > 1; i--)
    {
        std::swap(arr[i], arr[1]);
        headAdjust(arr, 1, i - 1);
    }
}

/**
 * BuildMaxHeap:建立大根堆
 * @param arr
 * @param len
 */
void Sort::buildMaxHeap(int arr[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        headAdjust(arr, i, len);
    }
}

/**
 * HeadAdjust:对元素k为子根的子树进行调整
 * @param arr
 * @param k
 * @param len
 */
void Sort::headAdjust(int arr[], int k, int len)
{
    arr[0] = arr[k];
    for (int i = 2 * k; i <= len; i *= 2)
    {
        if (i < len && arr[i] < arr[i + 1])
        {
            i++;
        }
        if (arr[0] > arr[i])
        {
            break;
        }
        {
            arr[k] = arr[i];
            k = i;
        }
    }
    arr[k] = arr[0];
}

auto B = static_cast<int*>(malloc((ARRAY_LENGTH + 1) * sizeof(int)));

/**
 * Merge:将两个有序表归并成一个有序表
 * @param arr
 * @param low
 * @param mid
 * @param high
 */
void Sort::merge(int arr[], int low, int mid, int high)
{
    int i, j, k;
    for (k = low; k <= high; k++)
    {
        B[k] = arr[k];
    }
    for (i = low, j = mid + 1, k = i; i < mid && j < high; k++)
    {
        if (B[i] <= B[j])
        {
            arr[k] = B[i++];
        }
        else
        {
            arr[k] = B[j++];
        }
    }
    while (i <= mid) arr[k++] = B[i++];
    while (j <= high) arr[k++] = B[j++];
}

/**
 * MergeSort:归并排序
 * 一种稳定的排序算法，适用于顺序存储和链式存储的线性表
 * @param arr
 * @param low
 * @param high
 */
void Sort::mergeSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

/**
 * CountSort:计数排序
 * 一种稳定的排序算法，更适用于顺序存储的线性表
 * @param arr_a
 * @param arr_b
 * @param n
 * @param k
 */
void Sort::countSort(int arr_a[], int arr_b[], int n, int k)
{
    int i, C[k];
    for (i = 0; i < k; i++)
    {
        C[i] = 0;
    }
    for (i = 0; i < n; i++)
    {
        C[arr_a[i]]++;
    }
    for (i = 1; i < k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (i = n - 1; i > 0; i--)
    {
        arr_b[C[arr_a[i]]] = arr_a[i];
        C[arr_a[i]] = C[arr_a[i]] - 1;
    }
}
